package com.demo.java.OD251_300.OD275;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【区间连接器】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146075024
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取区间信息
        String rangeStr = sc.nextLine();
        Integer[][] ranges = Arrays.stream(rangeStr.substring(1,
                        rangeStr.length() - 1).split("],\\[")) // 分割区间字符串
                .map(str -> Arrays.stream(str.split(","))
                        .map(Integer::parseInt) // 转换为整数
                        .toArray(Integer[]::new))
                .toArray(Integer[][]::new);

        // 读取已存在的连接线段长度
        String connectsStr = sc.nextLine();
        List<Integer> connects = Arrays.stream(connectsStr.substring(1,
                        connectsStr.length() - 1).split(","))
                .map(Integer::parseInt)
                .sorted(Comparator.reverseOrder()) // 逆序排序
                .collect(Collectors.toList());

        // 调用主函数计算最小连接数
        System.out.println(calculateMinimumNumOfLinks(ranges, connects));
    }

    /**
     * 计算最小连接数目
     *
     * @param ranges   所有的区间
     * @param connects 已存在的连接线段长度
     * @return 最小连接数目
     */
    public static int calculateMinimumNumOfLinks(Integer[][] ranges,
                                                 List<Integer> connects) {
        // 将区间数组按照左端点排序
        Arrays.sort(ranges, Comparator.comparingInt(a -> a[0]));

        // 将第一个区间加入连续区间列表
        LinkedList<Integer[]> rangesList = new LinkedList<>(Collections.singletonList(ranges[0]));

        // 待填补的空缺列表
        LinkedList<Integer> gaps = new LinkedList<>();

        // 遍历所有区间，尝试合并
        for (int i = 1; i < ranges.length; i++) {
            Integer[] last = rangesList.getLast();  // 获取最后一个合并区间
            int s1 = last[0], e1 = last[1];
            Integer[] range = ranges[i];
            int s2 = range[0], e2 = range[1];

            // 如果当前区间可以和上一个区间合并
            if (s2 <= e1) {
                rangesList.removeLast();  // 移除最后一个区间
                rangesList.addLast(new Integer[]{s1, Math.max(e1, e2)}); // 合并区间
            } else {
                gaps.addLast(s2 - e1);  // 记录空缺
                rangesList.addLast(range); // 新区间加入
            }
        }

        // 将空缺列表按长度从大到小排序
        gaps.sort((a, b) -> b - a);

        // 遍历已存在的连接线段，尝试填补空缺
        while (!connects.isEmpty() && !gaps.isEmpty()) {
            if (connects.remove(connects.size() - 1) >= gaps.getLast()) {
                gaps.removeLast(); // 填补一个空缺
            }
        }

        // 返回未填补空缺数量 + 1，即为最少需要的连接数
        return gaps.size() + 1;
    }
}